package problem76_Minimum_Window_Substring;

import java.util.HashMap;
import java.util.Map;

public class MySolution {
	public String minWindow(String s, String t) {
		Map<Character,Integer> directory=new HashMap<>();
		Map<Character,Integer> appear=new HashMap<>();
		for(char c:t.toCharArray()){
			directory.put(c, directory.containsKey(c)?directory.get(c)+1:1);
			appear.put(c, 0);
		}
		int left=0,right=0,minWindowStart=0,minWindowEnd=s.length();
		boolean hasAdded=false;
		while(right<s.length()){
			if(directory.containsKey(s.charAt(right))){
				if(!hasAdded)
					appear.put(s.charAt(right), appear.get(s.charAt(right))+1);
				if(containAll(directory,appear)){
					while(!directory.containsKey(s.charAt(left)))	left++;	//left jump to first char existed in t
					if(right-left<minWindowEnd-minWindowStart){
						minWindowStart=left;
						minWindowEnd=right;
					}
					//left jump to next char that exists in t
					if(left<right){
						appear.put(s.charAt(left),appear.get(s.charAt(left))-1);
						while(!directory.containsKey(s.charAt(++left)))	continue;
					}else{
						return s.charAt(left)+"";
					}
					hasAdded=true;
					continue;
				}
			}
			right++;
			hasAdded=false;
		}
		if(minWindowEnd-minWindowStart==s.length())	return "";
		return s.substring(minWindowStart,minWindowEnd+1);
    }
	
	public boolean containAll(Map<Character,Integer> directory,Map<Character,Integer> appear){
		for(Character c:directory.keySet()){
			if(appear.get(c)<directory.get(c))
				return false;
		}
		return true;
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().minWindow("BBNNAMM", "A"));
	}
}
